import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class L90 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 2};
        List<List<Integer>> lists = new Solution().subsetsWithDup(nums);
        for (List<Integer> list : lists) {
            System.out.println(list.toString());
        }
    }

    static class Solution {
        private List<List<Integer>> result = new ArrayList<>();
        private LinkedList<Integer> tmp = new LinkedList<>();

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            boolean[] used = new boolean[nums.length];
            Arrays.fill(used, false);
            backTrack(nums, 0, used);
            return result;
        }

        private void backTrack(int[] nums, int index, boolean[] used) {
            result.add(new LinkedList<>(tmp));

            if (index >= nums.length) {
                return;
            }

            for (int i = index; i < nums.length; i++) {
                if (i > index && nums[i] == nums[i - 1]) {
                    continue;
                }
                tmp.add(nums[i]);
                backTrack(nums, i + 1, used);
                tmp.removeLast();
            }
        }
    }
}
